1. Field
This disclosure relates to data stored in a data storage system and an improved architecture and method for storing data to and retrieving data from a data storage system made up of a large number of nodes and reliant upon a distributed hash table.
2. Description of the Related Art
A file system is used to store and organize computer data stored as electronic files. File systems allow files to be found, read, deleted, and otherwise accessed. File systems store files on one or more storage devices. File systems store files on storage media such as hard disk drives and solid-state storage devices.
Various applications may store large numbers of documents, images, audio, videos and other data as objects using a distributed data storage system in which data is stored in multiple locations.
Distributed hash tables (DHT or, plural, DHTs) are decentralized systems that enable information, such as computer data, to be stored within a group of servers. When file access is requested, a hashing function is used to point the request to a particular location (or locations) within the group of servers. In order to ensure that individual data sets remain available within the group of servers, prior art systems have enforced a blocking system in which data elements may not be written to when others are in the process of accessing those data elements.
When one of the servers fails, the DHT may point a request to a non-existent server within the group of servers. The pointers or other references must be updated once a determination is made that a server has failed.
For example, CHORD and ETNA DHT systems maintain a so-called key successor relationship with one other server local to that server. When the primary server fails, the key successor server, typically within one Internet “hop” away, fills the gap and is the next server looked-to by the system when using the CHORD or ETNA DHT. This approach has the unfortunate result of failing when a portion of the network serving the server and its key successor server goes down. While the servers may both have the appropriate data sets, they are inaccessible. Other portions of the network of the group of servers, if available, must be accessed in order to find the data sets. In addition, utilizing a key successor relationship results in placing the rectification load on the single key successor rather than distributing the load associated with rectification throughout the system.
Spreading the data around throughout the group of servers ensures that a single failure or localized failure is much less likely to result in a situation in which the system must stop access and/or writes to the data sets in order to recover. However, the distributed nature of the data in these systems introduce other problems, such as determining when one or more of a plurality of the servers is unavailable.
Throughout this description, elements appearing in figures are assigned three-digit reference designators, where the most significant digit is the figure number and the two least significant digits are specific to the element. An element that is not described in conjunction with a figure may be presumed to have the same characteristics and function as a previously-described element having a reference designator with the same least significant digits.